前言

昨天要處裡要返回台北的家當，所以只有簡單的介紹CFS 是什麼，以及CFS使用了什麼樣的資料結構，今天讓我們來看看到底CFS內部到底在做什麼事情。

vruntime

首先要了解的就是vruntime， 在CFS 裡面vruntime有著舉足輕重的地位，vruntime 代表的意義就是 virtual runtime，顧名思義就是行程到目前為止所運行的虛擬時間，所以對CFS 而言，為了公平起見，讓大家都能夠享有公平的運行時間，CFS會挑出vruntime最小的行程執行，也就是利用昨天講過的RB-tree的 left-most node。

那麼到底vruntime為何而生呢？ 先想想CFS 會挑選vruntime 最小的行程執行， 優先權比較高的行程，應該要擁有優先執行的權利，所以應該要找到一個方法，可以讓優先權比較高的行程，能夠擁有相對小的vruntime，才能夠讓這些行程優先執行。

在Linux 裡面會透過 p->se.load 讀取行程p的權重資訊， 在Linux內的權重，會用nice 值來表示，範圍由 -20~19 數字越大代表優先權越小，行程默認的 nice 值是0，可以理解成總共有40個階級。 如果有一個行程 nice值由0 變成1，代表該行程相對於其他nice 值是0 的行程，獲得的時間要少10% ，因此nice值少1 ，代表優先權上升，也代表獲得的CPU時間會多10%，Linux內規定，當nice值是0的時候，權重值是1024。

在nice值的計算上，Linux用了很有趣的技巧，與其每次都計算到底比例是多少，不如直接建一個表作近似就可以了!! 在vruntime的部分， Linux 用了兩個表，兩個列表都放在 kernel/shed/core.c 中

第一個是nice值對應的權重值

const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

第二個是 2^32 / 權重值

const u32 sched_prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

第二個表我們會在明天用到，第一個表就是用來近似的。
舉個簡單的例子，如果有兩個行程 nice值都是0，權重值都是1024，兩個行程都能得到50%的 CPU時間，如果其中一個行程的nice值變成1， 這樣他獲得的 CPU時間應該會變成 45% 約等於 820/(1024+820)， 反之nice 值為0的行程獲得的 CPU時間會是 55% 約等於 1024/(1024+820)，也因為使用了查表計算，能夠將計算簡化。

今天講完了權重表格的用法與CFS的概念，明天要看看到底 vruntime如何計算，以及第二個表格到底要做什麼用。